#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_OP 10

typedef struct Node{
    int data;
    Node *next;
}Node;

typedef struct LinkList{
    Node head, *tail;
}LinkList;

typedef struct Queue{
     LinkList *l;
    int count;
}Queue;

LinkList *initLinkList(){
     LinkList *l = (LinkList *)malloc(sizeof(LinkList));
     l->head.next = NULL;
     l->tail = &(l->head);
     return l;
}

void clearLinkList(LinkList *l){
    Node *p = l->head.next, *q;
    while(p){
        q = p->next; 
        free(p);
        p = q;
    } 
    free(l);
    return;
}

int frontList(LinkList *l){
    if(l->head.next == NULL) return 0;
    return l->head.next->data;
}

Node *getNewNode(int val){
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = NULL;
    return n;
}

int insertTail(LinkList *l, int val){
    Node *node = getNewNode(val);
    l->tail->next = node;
    l->tail = node;
    return 1;
}

int emptyList(LinkList *l){
    return l->head.next == NULL;
}

int eraseHead(LinkList *l){
    if(emptyList(l)) return 0;
    Node *t = l->head.next;
    l->head.next = l->head.next->next;
    if(t == l->tail) l->tail = &(l->head);
    free(t);
    return 1;
}

Queue *initQueue(){
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->l = initLinkList();
    q->count = 0;
    return q;
}

int empty(Queue *q){
    return q->count == 0;
}

int pop(Queue *q){
    eraseHead(q->l);
    q->count -= 1;
    return 1;
}

int push(Queue *q, int val){
    insertTail(q->l, val);
    q->count += 1;
    return 1;
}

int front(Queue *q){
    if(empty(q)) return 0;
    return frontList(q->l);
}    

void clearQueue(Queue *q){
    if(q == NULL) return;
    clearLinkList(q->l);
    free(q);
    return;
}

void outputQueue(Queue *q){
    printf("Queue: ");
    Node *n = q->l->head.next;
    for(int i = 0; i < q->count; i++){
        printf("%4d", n->data);
        n = n->next;
    }
    printf("\n\n");
    return;
}

int main(){
    srand(time(0));
    Queue *q = initQueue();
    for(int i = 0; i < MAX_OP; i++){
        // 0,1 pop, 2-4 push
        int op = rand() % 5; 
        int val = rand() % 100;
        switch (op) {
            case 0:
            case 1:
                printf("pop front of queue: %d\n", front(q));
                pop(q);
                break;
            case 2:
            case 3: 
            case 4: 
                printf("push %d to queue\n", val);
                push(q, val);
                break;
        }
        outputQueue(q);
    }
    
    clearQueue(q);
    return 0;
}